package 我的Java学习_算法基础.day_05;

import java.util.Arrays;

public class _086_字符串匹配之后缀数组_下 {
    public static Suff[] getSa3(String src) {
        int n = src.length();
        Suff[] sa = new Suff[n];
        for (int i = 0; i < n; i++) {
            sa[i] = new Suff(src.charAt(i), i);
        }
        Arrays.sort(sa);
        //rk是下标到排名的映射
        int[] rk = new int[n];//suffix array
        rk[sa[0].index] = 1;
        for (int i = 1; i < n; i++) {
            rk[sa[i].index] = rk[sa[i - 1].index];
            if (sa[i].c != sa[i - 1].c) rk[sa[i].index]++;
        }
        for (int k = 2; rk[sa[n - 1].index] < n; k *= 2) {
            final int kk = k;
            Arrays.sort(sa, (o1, o2) -> {
                int i = o1.index;
                int j = o2.index;
                if (rk[i] == rk[j]) {
                    if (i + kk / 2 >= n || j + kk / 2 >= n)
                        return -(i - j);//如果某个后缀不具有第二关键字，一定较小，索引靠后的更小
                    return rk[i + kk / 2] - rk[j + kk / 2];
                } else {
                    return rk[i] - rk[j];
                }

            });
            //更新rank
            rk[sa[0].index] = 1;
            for (int i = 1; i < n; i++) {//k代表截取范围，一开始只截一个字符，即每个字符参与排序，下次两个字符参与排序
                int i1 = sa[i].index;
                int i2 = sa[i - 1].index;
                rk[i1] = rk[i2];
                try {
                    if (!src.substring(i1, i1 + kk).equals((src.substring(i2, i2 + kk))))
                        rk[i1]++;
                } catch (Exception e) {
                    rk[i1]++;
                }
            }
        }
        return sa;
    }

    public static class Suff implements Comparable<Suff> {
        public char c;//后缀内容
        public int index;//后缀起始下标

        public Suff(char c, int index) {
            this.c = c;
            this.index = index;
        }

        @Override
        public int compareTo(Suff o) {
            return this.c - o.c;   //比较后缀（字典序）
        }

        @Override
        public String toString() {
            return "Suf{" + "str=" + c + ",index=" + index + '}';
        }
    }
}
